#include "BidirectionalLinkedList.h"
#include <cstdio>
#include <cstdlib>

int main(int argc, char const *argv[])
{
    DLinkList DL;
	DLinkList search;
	Dlist_head_insert(DL);
	//Dlist_tail_insert(DL);
	//3 4 5 6 7 9999
	PrintDList(DL);
	search=LocateElem(DL,3);
	if(search!=NULL)
	{
		printf("按序号查找成功\n");
		printf("%d\n",search->data);
	}
	DListFrontInsert(DL,3,99);
	PrintDList(DL);
	DListDelete(DL,6);
	PrintDList(DL);
	system("pause");

    return 0;
}

// 双向链表头插法
DLinkList Dlist_head_insert(DLinkList &DL)
{
    DNode *s;
    int x;
    DL = (DLinkList)malloc(sizeof(DNode));
    DL->next = nullptr;
    DL->prior = nullptr;
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (DLinkList)malloc(sizeof(DNode));
        s->data = x;
        s->next = DL->next;
        if (DL->next != nullptr)
        {
            DL->next->prior = s;
        }
        s->prior = DL;
        DL->next = s;
        scanf("%d", &x);
    }

    return DL;
}

// 双向链表尾插法
DLinkList Dlist_tail_insert(DLinkList &DL)
{
    DL = (DLinkList)malloc(sizeof(DNode));
    DLinkList r, s;
    int x;
    r = DL;
    DL->prior = nullptr;
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (DNode *)malloc(sizeof(DNode));
        s->data = x;
        r->next = s;
        s->prior = r;
        r = s; // 指向新的表尾节点
        scanf("%d", &x);
    }
    r->next = nullptr;

    return DL;
}

// 按序号查找结点值
DNode *GetElem(DLinkList DL, int i)
{
    if (i < 0)
        return nullptr;
    if (i == 0)
        return DL;
    int j = 1;
    DNode *p = DL->next;
    while(p && j <i) {
        p = p->next;
        j ++;
    }

    return p;
}

// 按值查找结点
DNode *LocateElem(DLinkList DL, ElemType e) {
    DNode *r = DL->next;
    while(r && r->data != e) {
        r = r->next;
    }

    return r;
}

// 新结点插入第i个位置
bool DListFrontInsert(DLinkList DL, int i, ElemType e) {
    if (i < 1)
        return false;
    DNode *r = GetElem(DL, i - 1);
    if (nullptr == r)
        return false;
    DLinkList s = (DNode*)malloc(sizeof(DNode));
    s->data = e;
    s->next = r->next;
    r->next->prior = s;
    s->prior = r;
    r->next = s;

    return true;
}

// 删除第i个结点
bool DListDelete(DLinkList DL, int i) {
    if (i < 1)
        return false;
    DNode *r = GetElem(DL, i);
    if (nullptr == r)
        return false;
    
    r->prior->next = r->next;
    if (nullptr != r->next)
        r->next->prior = r->prior;
    free(r);

    return true;
    
}

// 遍历链表
void PrintDList(DLinkList DL) {
    DL = DL->next;
    while (nullptr != DL) {
        printf("%3d", DL->data);
        DL = DL->next;
    }
    printf("\n");

    return;
}